package leetcode_2401_2500;

import java.util.Comparator;
import java.util.PriorityQueue;
import java.util.Queue;

public class LeeCode_2462 {
    public static void main(String[] args) {
        System.out.println(totalCost(new int[]{31,25,72,79,74,65,84,91,18,59,27,9,81,33,17,58}, 11, 2));
//        System.out.println(totalCost(new int[]{17, 12, 10, 2, 7, 2, 11, 20, 8}, 3, 4));
//        System.out.println(totalCost(new int[]{1,2,4,1}, 3, 3));
    }
    private static long totalCost(int[] costs, int k, int candidates) {
        int n = costs.length;
        PriorityQueue<int[]> queue = new PriorityQueue<>((o1, o2) -> o1[0] == o2[0] ? o1[1] - o2[1] : o1[0] - o2[0]);
        int l = candidates - 1, r = n - candidates;
        boolean flag = true;
        for (int i = 0; i <= l; i++) {
            queue.add(new int[]{costs[i], i});
        }
        for (int i = n - 1; i >= r; i--) {
            if (i <= l){
                flag = false;
                break;
            }
            queue.add(new int[]{costs[i], i});
        }
        long ans = 0;
        for (int i = 0; i < k; i++) {
            int[] p = queue.poll();
            int index = p[1];
            ans += p[0];
            if (index <= l){
                l++;
                if (flag && l >= r){
                    flag = false;
                }
                if (flag)
                    queue.add(new int[]{costs[l], l});
            }else {
                r--;
                if (flag && l >= r){
                    flag = false;
                }
                if (flag)
                    queue.add(new int[]{costs[r], r});
            }
        }
        return ans;
    }
}
